| 翻訳と辞書 |
| strong perfect graph theorem ： ウィキペディア英語版 |
strong perfect graph theorem
In graph theory, the strong perfect graph theorem is a forbidden graph characterization of the perfect graphs as being exactly the graphs that have neither odd holes (odd-length induced cycles) nor odd antiholes (complements of odd holes). It was conjectured by Claude Berge in 1961. A proof by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas was announced in 2002〔; .〕 and published by them in 2006.
The proof of the strong perfect graph theorem won for its authors a $10,000 prize offered by Gérard Cornuéjols of Carnegie Mellon University〔.〕 and the 2009 Fulkerson Prize.〔.〕
==Theorem statement==
A perfect graph is a graph in which, for every induced subgraph, the size of the maximum clique equals the minimum number of colors in a coloring of the graph; perfect graphs include many well-known graph classes including the bipartite graphs, chordal graphs, and comparability graphs. In his 1961 and 1963 works defining for the first time this class of graphs, Claude Berge observed that it is impossible for a perfect graph to contain an odd hole, an induced subgraph in the form of an odd-length cycle graph of length five or more, because odd holes have clique number two and chromatic number three. Similarly, he observed that perfect graphs cannot contain odd antiholes, induced subgraphs complementary to odd holes: an odd antihole with 2''k'' + 1 vertices has clique number ''k'' and chromatic number ''k'' + 1, again impossible for a perfect graphs. The graphs having neither odd holes nor odd antiholes became known as the Berge graphs.
Berge conjectured that every Berge graph is perfect, or equivalently that the perfect graphs and the Berge graphs define the same class of graphs. This became known as the strong perfect graph conjecture, until its proof in 2002, when it was renamed the strong perfect graph theorem.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「strong perfect graph theorem」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|